package com.hkb.josephusproblemlib;

import java.util.HashMap;

public class IsCircle {
    private static class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {

        //头节点单列出来，方便形成循环链表
        Node firstNode = new Node(1);
        Node x = firstNode;

        //建立单向链表
        for (int i = 2; i <= 10; i++) {
            x = (x.next = new Node(i));
        }
        //判断是否有环 快慢指针法
        boolean hasCircle = hasCircle1(firstNode);
        System.out.println("----------------------hasCircle=" + hasCircle);
        //组成环
        x.next = firstNode;
        hasCircle = hasCircle1(firstNode);
        System.out.println("----------------------hasCircleV1=" + hasCircle);
        hasCircle = hasCircle2(firstNode, 0);
        System.out.println("----------------------hasCircleV2=" + hasCircle);

    }

    /**
     * 判断是否有环 快慢指针法
     *
     * @return
     */
    public static boolean hasCircle1(Node headNode) {
        if (headNode == null) {
            return false;
        }

        Node slowPointer = headNode;
        Node fastPointer = headNode.next;

        // 快指针未能遍历完所有节点
        while (fastPointer != null && fastPointer.next != null) {
            slowPointer = slowPointer.next; // 遍历一个节点
            fastPointer = fastPointer.next.next; // 一次遍历两个节点

            // 已到链表末尾
            if (fastPointer == null) {
                return false;
            }
            if (slowPointer == fastPointer) {
                // 快指针追上慢指针，则证明存在环
                return true;
            }
        }

        return false;
    }

    private static HashMap<Node, Integer> footMap = new HashMap<>();

    /**
     * 判断是否有环 足迹法
     *
     * @param node
     * @return
     */
    public static boolean hasCircle2(Node node, int index) {
        if (node == null || node.next == null) {
            return false;
        }

        if (footMap.containsKey(node)) {
            return true;
        }
        footMap.put(node, index);
        return hasCircle2(node.next, ++index);
    }
}
